package main

type TrieNode struct {
	val      int
	children [26]*TrieNode
}

type MapSum struct {
	root *TrieNode
	m    map[string]int
}

func Constructor() MapSum {
	return MapSum{
		root: &TrieNode{},
		m:    make(map[string]int),
	}
}

func (this *MapSum) Insert(key string, val int) {
	exist := this.m[key]
	delta := val - exist
	this.m[key] = val
	node := this.root
	for _, ch := range key {
		if node.children[ch-'a'] == nil {
			n := &TrieNode{}
			node.children[ch-'a'] = n
		}
		node = node.children[ch-'a']
		node.val += delta
	}
}

func (this *MapSum) Sum(prefix string) int {
	node := this.root
	for _, ch := range prefix {
		if node.children[ch-'a'] == nil {
			return 0
		}
		node = node.children[ch-'a']
	}
	return node.val
}

func main() {
	m := Constructor()
	m.Insert("apple", 3)
	println(m.Sum("ap"))
	m.Insert("app", 2)
	m.Insert("apple", 2)
	println(m.Sum("ap"))
}
